package sword.chapter4LinkList;

import leetcode.t4LinkedList.ListNode;

/**
 * 删除倒数第k个结点
 * 要点：
 * 1. 前后指针 前指针移动k-1步，后指针指向头节点，然后以相同速度移动。
 * 2. 前指针到结尾后，后指针的next 指向 next.next
 *
 *        x     |
 * front  1 2 3 4 5 6 null
 * back 0 1 2 3 4 5 6 null
 *
 * front 先移动3步   节点位置：x+3 = 4
 * back  节点位置：x-1 = 0
 * 循环3次 x+3+3 = null x-1+3=3 3的下一个指向5（删除了4 倒数第3个）
 *
 * @author K
 * @date 2021/11/24 11:33
 */
public class S21RemoveNthFromEnd {

    public static void main(String[] args) {
        ListNode node = new ListNode(1);
        for (int i = 0; i < 5; i++) {
            node.put(node, i + 2);
        }
        ListNode linkNode = s21(node, 3);
        System.out.println();
    }

    public static ListNode s21(ListNode head, int k) {
        ListNode dummy = new ListNode(0);
        dummy.next = head;

        ListNode front = head;
        for (int i = 0; i < k; i++) {
            front = front.next;
        }

        ListNode back = dummy;
        while (back != null && front != null) {
            front = front.next;
            back = back.next;

            if (front == null) {
                back.next =back.next.next;
                break;
            }
        }

        return dummy.next;
    }

}
